The present invention relates to a data processing system and data processing method for primality checking, and particularly to a technique useful in the efficient generation of cryptographic keys to be used in e.g. the framework of a public key cryptosystem.
Public key cryptosystems have gained a wide recognition, and are now commonly used in many applications, such as banking or electronic commerce, where they can be used to digitally sign documents, encrypt data, exchange keys between users communicating over insecure network and others. RSA is a de-facto standard for public key cryptography, and has gained widespread popularity in applications where a digital signature or public key encryption are required. For instance, the use of RSA is recommended by the EMV (Europay-Mastercard-Visa) consortium for credit cards. More precisely, EMV recommends RSA with a key length of 1024 bits until 2010, and 2048-bit keys after that.
In RSA, messages are encoded as n-bit integers. An RSA public key consists of a public exponent E, which is typically small, and an n-bit public modulus N, and the RSA private key is an n-bit integer D such that E*D=1 mod (P−1)*(Q−1), where P and Q are secret prime numbers satisfying P*Q=N, and the sign “*” denotes multiplication. Now, for any message such that 0<=M<N, (MeE)D mod N=M holds. For example, if Alice is a holder of the RSA key (E,N), D, and Bob whishes to send an encrypted message M to Alice, Bob computes C=ME mod N, and sends the ciphertext to Alice. Then, Alice computes CD=(ME)D=M mod N and recovers the plaintext. It can be seen that the core operation in RSA is the exponentiation XY mod N. When N is large, for instance 2048 bits, such exponentiation takes time. In order to accelerate RSA operations, one can take advantage of the Chinese Remainder Theorem, which states that the exponentiation CD mod N can be replaced with two exponentiations modulo P and modulo Q. Since N=P*Q and P and Q have about half the size of the modulus N, the Chinese Remainder Theorem approach (RSA-CRT) is much faster in practice. In RSA-CRT, the encryption procedure is the same as in standard RSA: C=ME mod N. The difference is in the decryption procedure. The following definitions are given, for example:DP=D mod P−1=E−1 mod P−1,DQ=D mod Q−1=E−1 mod Q−1, andQinv=Q−1 mod P, 
where Z=X−1 mod Y is an integer 1<=Z<Y satisfying Z*X=1 mod Y. Then, RSA-CRT decryption is executed by computer as follows:MP=CDP mod P, MQ=CDQ mod Q, andM=MQ+Q*[Qinv*(MP−MQ)mod P]. 
Therefore, the keypair of RSA consists of:
the public key (E,N),
the private key D for standard RSA, and (P, Q, DP, DQ, Qinv) for RSA-CRT.
The length of an RSA key depends on the number of bits of the public modulus N. For example, in 2048-bit RSA, the public modulus N has 2048 bits, and generally, the two primes P and Q each have 1024 bits, so that N=P*Q. In order to issue RSA keys, two random primes P and Q are selected, and other key elements are derived from the two primes. A step for generating a random prime proceeds as follows. First, a random integer is selected, and then this random number is tested for primality, for example with the Fermat test. If the random number does not pass the primality test, it is updated with a new prime candidate. How to update differs from one method to the other; for example, the first random integer may be replaced with a new random integer, or alternatively it can be incremented. The step of generating random primes is the most computationally expensive task in generation of RSA keys.
In the past, RSA key generation in smartcards was out of question because their computing power was too low to handle such costly operations. As a consequence, RSA keys were calculated on a powerful workstation, and copied on the smartcard. However, recent smartcards benefit from hardware accelerators dedicated to public key cryptography; with these cryptographic coprocessors, it becomes practical to generate keys in smartcards. This approach has two advantages. The first one is that there is no single point of failure, unlike the case where keys were generated on a workstation: if the workstation is compromised, all generated keys are consequently put in danger. The second advantage is that the card issuer need not know the secret key. In case of dispute, the card issuer cannot be regarded to be responsible for leaking secret keys or misusing them.